package other;

import java.util.ArrayList;
import java.util.List;

/**题目：给定一个字符串，要求把该字符串切割为每个子串都是回文字符串
 * y: aab
 *  [['a','a','b'],['aa','b']]
 * @Author Gavin
 * @date 2022.01.06 22:41
 */
public class solution_5 {
    /**
     * 解题思路：
     * 利用递归进行切割字符串
     * 利用两个下标（i,j），判断(i,j)是不是回文字符串，如果是
     * 就递归判断（i,j）的位置,此时的i为上一次的j的位置后一位
     * y: aab
     *  i=0,j=0
     *  i=1,j=1
     *  i=2,j=2
     *
     *  i=0,j=1
     *  i=2,j=2
     */
    public List<List<String>> solution(String s){
        List<List<String>> result=new ArrayList<>();
        if(s==null||s.length()==0)return result;
        int n=s.length();
        //1.首先利用一个二维数组来保存字符下标位置是否是回文串
        //当然也可以写一个函数，利用双指针的方式，实时判断某一个字符串
        //是否是回文串
        boolean[][] d=new boolean[n][n];
        for (int i =n-1; i>=0; --i) {
            for (int j = i; j <n ; j++) {
                if(i==j)d[i][j]=true;
                else {
                    boolean b = s.charAt(i) == s.charAt(j);
                    if(i+1==j)d[i][j]= b;
                    else d[i][j]= b &&d[i+1][j-1];
                }
            }
        }
        partition(s,0,d,result,new ArrayList<>());
        return result;
    }
    private void partition(String s,int start,boolean[][]d,List<List<String>> result,List<String>elem){
        if(start>=s.length()-1){//如果开始下标达到了字符串末尾了，说明就产生了一次正确的分割了
            result.add(new ArrayList<>(elem));
        }else{
            for (int end = start; end < s.length(); end++) {
                if(d[start][end]){//判断是否是回文串
                    String subStr=s.substring(start,end+1);
                    elem.add(subStr);
                    //递归分割后面的字符串
                    partition(s,end+1,d,result,elem);
                    //递归完一次就代表字符串已经被切割了一次了，然后需要移除每次
                    //递归添加到elem里面的元素，需要保证第二次循环开始的时候
                    //elem为empty
                    elem.remove(elem.size()-1);
                }
            }
        }
    }

    public static void main(String[] args) {
        System.out.println("abc".substring(0,1));
    }
}
